Inplace FFT & IFFT shifting

This tests out an in-place implementation of the ifft and fft shifts for even- and uneven-sized dimensions. To be implemented in bullseye's FFT machine Grids with even dimensions only require that quadrants 1 & 3 and 2 & 4 be swapped (the fftshift == ifftshift for even dimensions), but for the uneven case this is not as trivial. Here we opt do separate the rotations in the horizontal direction and vertical directions. This implementation will work for any combination of even and odd dimensions (vertical and/or horizontally)



In [161]:

    
import numpy as np



In [162]:

    
xn = 6
yn = 6
original = np.arange(1,xn*yn + 1,dtype=np.float).reshape([yn,xn])
print original









    



[[  1.   2.   3.   4.   5.   6.]
 [  7.   8.   9.  10.  11.  12.]
 [ 13.  14.  15.  16.  17.  18.]
 [ 19.  20.  21.  22.  23.  24.]
 [ 25.  26.  27.  28.  29.  30.]
 [ 31.  32.  33.  34.  35.  36.]]



In [163]:

    
print "THE IFFT SHIFT SHOULD GIVE:"
model_ifft_shift = np.fft.ifftshift(original)
print model_ifft_shift









    



THE IFFT SHIFT SHOULD GIVE:
[[ 22.  23.  24.  19.  20.  21.]
 [ 28.  29.  30.  25.  26.  27.]
 [ 34.  35.  36.  31.  32.  33.]
 [  4.   5.   6.   1.   2.   3.]
 [ 10.  11.  12.   7.   8.   9.]
 [ 16.  17.  18.  13.  14.  15.]]



In [164]:

    
print "THE FFT SHIFT SHOULD GIVE:"
model_fft_shift = np.fft.fftshift(original)
print model_fft_shift









    



THE FFT SHIFT SHOULD GIVE:
[[ 22.  23.  24.  19.  20.  21.]
 [ 28.  29.  30.  25.  26.  27.]
 [ 34.  35.  36.  31.  32.  33.]
 [  4.   5.   6.   1.   2.   3.]
 [ 10.  11.  12.   7.   8.   9.]
 [ 16.  17.  18.  13.  14.  15.]]



In [165]:

    
def ifftshift(mat):
    T = np.copy(mat)
    half_x = T.shape[1] // 2
    half_y = T.shape[0] // 2
    odd_offset_x = 1 if T.shape[1] % 2 != 0 else 0
    #rotate all the rows right
    for iy in range(0,T.shape[0]):
        swap_mid = T[iy,half_x]
        for ix in range(0,half_x):
            ix_reverse = half_x - 1 - ix
            swap_x = T[iy,half_x + ix_reverse + odd_offset_x]
            T[iy,half_x + ix_reverse + odd_offset_x] = T[iy,ix_reverse]
            T[iy,ix_reverse+odd_offset_x] = swap_x
        T[iy,0] = swap_mid #doesn't matter for the even case
        
    odd_offset_y = 1 if T.shape[0] % 2 != 0 else 0
    #rotate all the columns down
    for ix in range(0,T.shape[1]):
        swap_mid = T[half_y,ix]
        for iy in range(0,half_y):
            iy_reverse = half_y - 1 - iy
            swap_y = T[half_y + iy_reverse + odd_offset_y,ix]
            T[half_y + iy_reverse + odd_offset_y,ix] = T[iy_reverse,ix]
            T[iy_reverse+odd_offset_y,ix] = swap_y
        T[0,ix] = swap_mid #doesn't matter for the even case
    
    return T



In [166]:

    
assert np.all(model_ifft_shift == ifftshift(original)), "Test case failed"



In [167]:

    
def fftshift(mat):
    T = np.copy(mat)
    half_x = T.shape[1] // 2
    half_y = T.shape[0] // 2
    odd_offset_x = 1 if T.shape[1] % 2 != 0 else 0
    #rotate all the rows right
    for iy in range(0,T.shape[0]):
        swap_mid = T[iy,half_x]
        for ix in range(0,half_x):
            swap = T[iy,ix] #in case this dimension is even
            T[iy,ix] = T[iy,half_x + ix + odd_offset_x]
            T[iy,half_x + ix] = swap 
        if T.shape[1] % 2 != 0:
            T[iy,T.shape[1]-1] = swap_mid

    odd_offset_y = 1 if T.shape[0] % 2 != 0 else 0
    #rotate all the columns down
    for ix in range(0,T.shape[1]):
        swap_mid = T[half_y,ix]
        for iy in range(0,half_y):
            swap = T[iy,ix] #in case this dimension is even
            T[iy,ix] = T[half_y + iy + odd_offset_y,ix]
            T[half_y + iy,ix] = swap
        if T.shape[0] % 2 != 0:
            T[T.shape[0]-1,ix] = swap_mid
    return T



In [168]:

    
assert np.all(model_fft_shift == fftshift(original)), "Test case failed"



In [168]: